package review;

import org.junit.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class T22 {
    @Test
    public void test1() {
//        System.out.println(generateParenthesis_BFS(3));
        System.out.println(generateParenthesis_DFS(3));

    }

//    ==========================DFS================================
    public List<String> generateParenthesis_DFS(int n) {
        ArrayList<String> ans = new ArrayList<>();
        DFS("", n, n,ans);
        return ans;
    }

    private void DFS(String s, int left, int right,ArrayList<String> ans) {
        if (left > right) { //如果左括号的剩余量比右括号少，不符合情况
            return;
        }

        if (left > 0) {    //如果左括号剩余量不为0
            DFS(s + "(", left - 1, right,ans);
        }

        if (right > 0 && left < right) {
            DFS(s + ")", left, right - 1,ans);
        }

        if (left == 0 && right == 0) {
            ans.add(s);
            return;
        }
    }
//    -----------------------------------------------------------------------



//    ---------------------------BFS-------------------------------
    public List<String> generateParenthesis_BFS(int n) {
        ArrayList<String> ans = new ArrayList<>();  //存储合法的括号串个数

        Queue<Node> queue = new LinkedList<>(); //LinkedList是Queue接口的实现类

        queue.offer(new Node(n, n, ""));
        while (!queue.isEmpty()) {
            Node node = queue.poll();//出队

            if (node.left == 0 && node.right == 0) { //找到一个合法的串
                ans.add(node.res);
            }

            if (node.left > 0) {    //左边括号有剩余可以加入
                queue.offer(new Node(node.left - 1, node.right, node.res + "("));
            }

            if (node.right > 0 && node.right > node.left) { //右括号有剩余可以加入
                queue.offer(new Node(node.left, node.right - 1, node.res + ")"));
            }
        }
        return ans;
    }
}


class Node{
    int left;   //左括号剩余个数
    int right;  //右括号剩余个数
    String res; //目前的括号串

    public Node(int left, int right, String res) {
        this.left = left;
        this.right = right;
        this.res = res;
    }
}